package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    // Reverses the order of the elements in the specified list
    public static void reverse(MyList list) {
        int mid = list.size() / 2;
        int n = list.size() - 1;
        for (int i = 0; i < mid; i++) {
            Object tmp = list.get(i);
            list.set(i, list.get(n - i));
            list.set(n - i, tmp);
        }
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key) {
        //Если элемент найден, то возвращается его индекс. 
        //Если не найдет, то возвращается отрицательное значение,
        //вычисляемое по следующей формуле: 
        //(-(insertion point) - 1), где insertion point - индекс того места 
        //в массиве, где должен был бы быть указанный элемент.
        Object[] array = list.toArray();

        return binarySearch(array, key, 0, array.length - 1);
    }

    private static int binarySearch(Object[] array, Object key,
            int left, int right) {
        if (left == right) {
            if (array[left].equals(key)) {
                return left;
            } else {
                return -left - 1;
            }
        }
        int mid = left + (right-left) / 2;
        int compare = ((Comparable) array[mid]).compareTo(key);
        if (compare == 0) { //equals
            return mid;
        } else {
            if (compare > 0) { //key less
                return binarySearch(array, key, left, mid - 1);
            } else {
                return binarySearch(array, key, mid + 1, right);
            }
        }
    }

    private static int binarySearch(Object[] array, Object key,
            int left, int right, Comparator cp) {
        if (left == right) {
            if (array[left].equals(key)) {
                return left;
            } else {
                return -left - 1;
            }
        }
        int mid = left + (right-left) / 2;
        int compare = cp.compare(array[mid], key);
        if (compare == 0) { //equals
            return mid;
        } else {
            if (compare < 0) { //key less
                return binarySearch(array, key, left, mid - 1);
            } else {
                return binarySearch(array, key, mid + 1, right);
            }
        }
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key, Comparator cp) {
        Object[] array = list.toArray();
        return binarySearch(array, key, 0, array.length - 1, cp);
    }
}
